public class Solution {
    public static int sum(int i, int j){
        int s=0;
        while(i!=0){
            s = s+i%10;
            i = i/10;
        }
        while(j!=0){
            s = s+j%10;
            j = j/10;
        }
        return s;
    }
    public static int moving(int threshold, int rows, int cols, int i, int j, int[] visited){
        if(i<0 || i>=rows || j<0 || j>=cols)
            return 0;
        if(visited[i*cols+j] ==0 && sum(i,j)<=threshold){
            visited[i*cols+j] = 1;
            return 1+moving(threshold,rows,cols,i-1,j,visited)
                    +moving(threshold,rows,cols,i+1,j,visited)
                    +moving(threshold,rows,cols,i,j-1,visited)
                    +moving(threshold,rows,cols,i,j+1,visited);
        }else{
            return 0;
        }
    }
    public static int movingCount(int threshold, int rows, int cols)
    {
        int[] visited = new int[rows*cols];
        return moving(threshold,rows,cols,0,0,visited);
//                if(sum(rows,cols)<threshold)
//                    count++;

    }
    public static void main(String args[]){
        int threshold = 5;
        int rows = 10;
        int cols = 10;
        int b = movingCount(threshold,rows,cols);
        System.out.println(b);
    }



}

